KURZUS: Alkalmazott operációkutatás

MODUL: II. modul: Egészértékű programozási feladat fogalma és grafikus megoldása. Néhány nevezetes egészértékű modell

7. lecke: Hozzárendelési feladat

|  | Tanulási útmutató
| A hozzárendelési feladat definíciója, matematikai modellje a tankönyv 5.4. fejezetében található. Az itt bemutatott példán keresztül jól érthető lesz a probléma lényege és a használt jelölések tartalma.
| Könnyen észreveheti, hogy ez is egy speciális lineáris programozási modell (speciális elosztási feladat), amely szintén megoldható szimplex módszerrel, így a Solver programmal is. Mégis érdemes megismerkedni egy speciális matematikai megoldással - szétválasztás és korlátozás módszerével - mert nagyobb méretű feladatok is könnyen kezelhetők ezzel az eljárással.
| Tevékenységek
| Figyelmesen olvassa el a hozzárendelési feladat definícióját, modelljét. Jól jegyezze meg a modell paramétereit és gazdasági jelentéseit a tankönyvben található példán keresztül.
| Jegyezze jól meg a költségmátrix elemeinek jelentését. Jegyezze meg a redukció szó értelmét és lássa be, hogy a redukált mátrix tartalma egyezik az eredetivel, de könnyebben kezelhető az optimális megoldás vizsgálata szempontjából.
| Ha megértette a redukált mátrix értelmét, akkor érdemes a tankönyv 5.4.3. alfejezetéhez lapozni, hogy mindjárt az általánosabb feladatot is megértse: hogyan járjunk el, ha a munkások száma nem egyezik a munkák számával, illetve ha valamelyik munkás valamelyik munkát nem végezheti el.
| Ha a redukált mátrixról nem olvasható le optimális megoldás, akkor alkalmazzuk a szétválasztás és korlátozás módszert. Ennek lényegét a tankönyvben találja. Gondolja át, és fogalmazza meg az x i j , c i j , r i j , és k jelölések tartalmi jelentését. Kövesse végig a számítást úgy, hogy egy külön lapon Ön is írja a változásokat.
| Gyakorolja az általános esetet is. Gondolja át, és fogalmazza meg az M szimbólum jelentését! Vegye észre, ha a mátrix egy elemét megváltoztatja, akkor egész más lehet az eljárás útja.
| Helyezze el a költségmátrixot és az ismeretlenek mátrixát a szállítási feladatoknál megtanult módon Excel-táblán, hiszen ez egy speciális szállítási feladat.
| Itt x i j jelenti, hogy az i-edik munkás elvégzi a j-edik munkát vagy sem. Az x i j ebben az esetben egy bináris változó, értéke 1, ha a munkás elvégzi a munkát, 0, ha nem végzi el.
| "Az i-edik munkás valamelyik munkát elvégzi" magyar mondatnak matematikai megfelelője:
| x i 1 + x i 2 +...+ x i n =1, ahol i=1, 2,...,n.
| A munkás csak az egyik munkát végzi el, ennek a változónak az értéke 1, a többi 0, így lehet az összegük 1.
| "A j-edik munkát valamelyik munkás elvégzi" magyar mondat megfelelője:
| x 1 j + x 2 j +...+ x n j =1, ahol j=1, 2,...,n.
| A célfüggvény pedig:
| k=8 x 11 +10 x 12 +7 x 13 +8 x 14 +.....+11 x 54 +18 x 55 →min⁡
| lesz. Ezt érdemes a SZORZATÖSSZEG függvénnyel előállítani.
| Hívja meg a Solver programot és jelölje be a célfüggvény cellájának helyét, a változók mátrixának tartományát, feltételi egyenlőségeket adja hozzá a feltételekhez. Itt jelölje be, hogy a változók mátrixának tartománya bináris lehet. Ne felejtse el a beállításokat: Lineáris modell, nemnegatív feltételezés.
| (Ennek a feladatnak szinte mindig van optimális megoldása!)
| Követelmények
| Önállóan fel tudja írni egy adott (általános) hozzárendelési feladat matematikai modelljét. Meg tudjon oldani egy költségmátrixszal adott, speciális feltételeket is tartalmazó feladatot szétválasztás és korlátozás módszerével. Meg tudja keresni - egy Excel-táblán megadott költségmátrix ismeretében - a hozzárendelési feladat optimális megoldását.

|  | Bemutató feladat
| Négy munkás között kell 4 feladatot elvégeztetni úgy, hogy a termelés költsége a lehető legkisebb legyen. Az első munkás a második feladatot nem tudja ellátni, a harmadik munkás pedig a harmadik feladatot. A második munkásnak mindenképpen kell munkát kapnia. A költségek az alábbiak (eFt):
6 | 8 | 3 | 4
5 | 2 | 6 | 7
3 | 4 | 2 | 8
2 | 5 | 3 | 6
| Melyik munkás melyik feladatot kapja meg, hogy a költségek minimálisak legyenek.
| Megoldás: Vigyük be az adatokat az Excel táblázatkezelőbe! Az "M" azt jelenti, hogy nem tudja elvégezni. Az Excelbe ilyenkor egy nagy számot írunk.
| Ezután indítsuk el a Solvert, és írjuk be a korlátozó feltételeket az alábbi módon:
| Korlátozó feltételek (egyenként kell felvenni őket):
| $B$12:$E$12=1 $B$7:$E$10=bináris érték $G$7:$G$10=1
| Nyomjuk meg a megoldás gombot!

|  | Önellenőrző feladat
| 1. A fent említett három követelménynek megfelelő feladat az alábbi:
| Egy üzemben 4 munkásnak kell kiosztani 3 feladatot úgy, hogy az összes költség a lehető legkisebb legyen. A 2. munkás a 2. munkafeladatot nem tudja elvégezni, de a többi munkás minden feladatot el tud végezni.
| A költségeket a [ 3 7 10 9 1 8 2 5 6 11 7 4 ] 1000 Ft költségmátrix szemlélteti.
| További feltétel:
| A harmadik munkás a sógorom, ezért ő mindenképpen kapjon munkát!
| Kérdés: Melyik munkás melyik munkát kapja, hogy az összes költség a lehető legkisebb legyen?
| Megoldás: Bevezetünk egy névleges munkafeladatot. Jelölje x i j azt, hogy az i-edik munkás a j-edik munkát elvégzi-e vagy nem. Azaz x i j ≥0 és x i j ∈[ 0; 1 ]
| A munkásokra vonatkozó feltételek:
| x 11 + x 12 + x 13 + x 14 = 1 x 21 + x 22 + x 23 + x 24 = 1 x 31 + x 32 + x 33 + x 34 = 1 x 41 + x 42 x 43 + x 44 = 1 x 34 = 0 x 22 = 0
| Megjegyzés: az x34 azért =0, mert így a sógorom nem kaphatja meg a névleges munkát, azaz biztosan kap feladatot.
| A munkákra vonatkozó feltételek:
| x 11 + x 21 + x 31 + x 41 = 1 x 12 + x 22 + x 32 + x 42 = 1 x 13 + x 23 + x 33 + x 43 = 1 x 14 + x 24 + x 34 + x 44 = 1
| Költségfüggvény:
| k=3 x 11 +7 x 12 +10 x 13 +..... +11 x 41 +7 x 42 +4 x 43 → min⁡
| Oldja meg a szétválasztás és korlátozás módszerével!
| Vegyen elő egy négyzetrácsos lapot és oldja meg a feladatot. Az alábbi részeredményeket közölje:
| a) Írja fel a feladat kiegészített költségmátrixát
| b) Írja ide a redukált mátrixot. Oszlop szerint kezdje a redukciót!
| c) Adja meg a redukció értékét! A redukció értéke:
| d) Állítsa elő az optimális megoldást!
| Írja be a változók mátrixába az optimális megoldást: A változók értéke 0 vagy 1 lehet!
| e) Adja meg az optimális megoldás k o p t értékét! k o p t =
| 2. Oldja meg a feladatot Solver program segítségével!
| Helyezze el az induló költségmátrixot egy Excel-táblán. A kiegészített költségmátrix első eleme a B3 cellában legyen! Az M helyébe egy nagy számot írjon!
| A változók mátrixának első eleme a B10, a célfüggvény értéke C15 cellában legyen! A feltételek bal oldalának képletét a kiegészített mátrix melletti, illetve alatti cellákba képezze a Σ függvénnyel. Hívja meg a Solver programot, és rámutatással vigye be a kért adatokat.
| a) Írja ide a mátrixba az optimális megoldást! Az értéke 0 vagy 1 lehet!
| b) Adja meg az optimális megoldás költségét! Az optimális megoldás költsége: eFt.